package com.company;

import java.util.Arrays;
import java.util.Random;

/**
 * @date : 2021/12/8 18:54
 * 基数排序问题
 */
public class P008_RadixSort {

    public static class RadixSort {

        public static void main(String[] args) {
            for (int i = 0; i < 50000; i++) {
                int[] arr = generateRandomArray(100, 100);
                int[] newArr = new int[arr.length];
                System.arraycopy(arr, 0, newArr, 0, arr.length);
                radixSort(arr);
                Arrays.sort(newArr);
                if (!Arrays.equals(arr, newArr)) {
                    System.out.println("---start---");
                    System.out.println(Arrays.toString(arr));
                    System.out.println(Arrays.toString(newArr));
                    System.out.println("----end----");
                }
            }
        }

        public static int[] generateRandomArray(int maxSize, int maxValue) {
            int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
            for (int i = 0; i < arr.length; i++) {
                arr[i] = new Random().nextInt(maxValue)+1;
            }
            return arr;
        }

        /**
         * 递归找出数组的最大值
         *
         * @param array 数组
         * @param low   左边界，索引值
         * @param high  右边界，数组的长度
         * @return 数组的最大值
         */
        public static int findMax(int[] array, int low, int high) {
            // 如果数组只有一个数，那么最大值就是该数
            if (low == high) {
                return array[low];
            } else {
                int a = array[low];
                int b = findMax(array, low + 1, high);
                return Math.max(a, b);
            }
        }

        public static void radixSort(int[] array) {
            int max = findMax(array, 0, array.length - 1);
            // 需要遍历的次数由数组的最大值的位数来决定
            for (int i = 1; max / i > 0; i *= 10) {
                int[][] buckets = new int[array.length][10];
                // 获取每一位数字（个、十、百……分配到桶子里）
                for (int j = 0; j < array.length; j++) {
                    int num = (array[j] / i) % 10;
                    // 将其放入桶里
                    buckets[j][num] = array[j];
                }

                // 回收桶子里的元素
                int k = 0;

                for (int j = 0; j < 10; j++) {
                    // 对每一个桶子里的元素进行回收
                    for (int l = 0; l < array.length; l++) {
                        // 如果桶子里有元素，就会回收（数据初始化为0）
                        if (buckets[l][j] != 0) {
                            array[k++] = buckets[l][j];
                        }
                    }
                }
            }
        }
    }
}
